package com.demo.java.OD101_150.OD138;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【和最大子矩阵】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145730172
 */
public class OdMain {

    // 主函数，负责读取输入并调用解决问题的函数
    public static void main(String[] args) {
        // 创建Scanner对象用于读取输入
        Scanner scanner = new Scanner(System.in);

        // 读取输入的第一行，表示矩阵的行数和列数
        String[] split = scanner.nextLine().split(" ");
        int numRows = Integer.parseInt(split[0]);  // 矩阵的行数
        int numCols = Integer.parseInt(split[1]);  // 矩阵的列数

        // 创建二维数组来存储输入的矩阵
        int[][] inputMatrix = new int[numRows][numCols];

        // 读取矩阵的每一行数据
        for (int i = 0; i < numRows; ++i) {
            String[] nums = scanner.nextLine().split(" ");
            for (int j = 0; j < nums.length; j++) {
                // 将每行的数字填充到二维数组中
                inputMatrix[i][j] = Integer.parseInt(nums[j]);
            }
        }

        // 调用 solveMethod 方法来计算矩阵的最大子矩阵和
        int maxSum = solveMethod(numCols, numRows, inputMatrix);

        // 输出结果
        System.out.println(maxSum);

        // 关闭Scanner对象
        scanner.close();
    }

    // solveMethod 方法用于计算矩阵的最大子矩阵和
    private static int solveMethod(int numCols, int numRows, int[][] inputMatrix) {
        int maxSum = 0;  // 初始化最大和为0
        int[] colSum = new int[numCols];  // 存储每一列的和

        // 遍历每一个可能的上边界（i为上边界的索引）
        for (int i = 0; i < numRows; ++i) {
            // 每次外层循环都重新初始化 colSum 数组
            for (int k = 0; k < numCols; k++) {
                colSum[k] = 0;
            }

            // 遍历从当前上边界到每个可能的下边界（j为下边界的索引）
            for (int j = i; j < numRows; j++) {
                // 将当前行的元素加到对应列的累加和
                for (int k = 0; k < numCols; k++) {
                    colSum[k] += inputMatrix[j][k];
                }
                // 计算当前列和的最大子数组和，并与当前最大和比较
                int maxColSum = maxSum(numCols, colSum);
                if (maxColSum > maxSum) {
                    maxSum = maxColSum;  // 更新最大和
                }
            }
        }
        return maxSum;  // 返回最大子矩阵和
    }

    // maxSum 方法用于计算一维数组的最大子数组和（类似于Kadane算法）
    private static int maxSum(int numCols, int[] a) {
        int maxSum = 0;  // 初始化最大和为0
        int currentSum = 0;  // 当前和

        // 遍历一维数组，使用Kadane算法计算最大子数组和
        for (int i = 0; i < numCols; ++i) {
            currentSum += a[i];  // 加上当前元素

            // 如果当前和大于最大和，则更新最大和
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }

            // 如果当前和为负数，则重置当前和为0，表示从下一个元素开始新的子数组
            if (currentSum < 0) {
                currentSum = 0;
            }
        }
        return maxSum;  // 返回最大子数组和
    }
}
